package offer;

@FunctionalInterface
public interface BestRotation {
    int bestRotation(int[] nums);
}

class BestRotationTest{
    static final int[] TEST_01 = new int[]{2,3,1,4,0};

    public static void main(String[] args) {
        new BestRotationImpl1().bestRotation(TEST_01);
    }
}

/**
 * 暴力解法
 */
class BestRotationImpl1 implements BestRotation{

    @Override
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] scores = new int[n];
        scores[0] = calcScore(nums);
        for(int i = 1; i < n; i++) {
            int[] clone = nums.clone();
            rotate(clone, i);
            scores[i] = calcScore(clone);
        }
        int maxScore = scores[0];
        int maxIndex = 0;
        for (int i = 1; i < n; i++) {
            if(scores[i] > maxScore){
                maxScore = scores[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
    private void rotate(int[] nums, int k){
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }
    private void reverse(int[] nums, int left, int right){
        while(left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    private int calcScore(int[] nums){
        int score = 0;
        for (int i = 0; i < nums.length; i++) {
            if(i >= nums[i]){
                score++;
            }
        }
        return score;
    }
}

class BestRotationImpl2 implements BestRotation{
    @Override
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] scores = new int[n];
        int maxIndex = 0, maxScore = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = i - nums[i];
        }
        for (int k = 0; k < n; k++) {
            int[] clone = nums.clone();
            for (int j = 0; j <= k - 1; j++) {
                clone[j] = clone[j] + n - k;
            }
            for (int j = k; j < n; j++) {
                clone[j] = clone[j] - k;
            }
            int count = 0;
            for (int i = 0; i < n; i++) {
                if(clone[i] >= 0){
                    count++;
                }
            }
            scores[k] = count;
            if(scores[k] > maxScore){
                maxIndex = k;
                maxScore = scores[k];
            }
        }
        return maxIndex;
    }
}
